'''
https://leetcode.cn/problems/minimize-deviation-in-array/description/
'''
import heapq
from typing import List
from sortedcontainers import SortedSet

class Solution:

    # 奇数最多一次改变，就开始震荡了
    # 偶数最多k次改变，就开始震荡了
    # 堆实现
    def minimumDeviation(self, nums: List[int]) -> int:
        heap = [-num if num & 1 == 0 else -(num << 1) for num in nums]
        heapq.heapify(heap)

        min_v, max_v = -max(heap), -heap[0]
        ans = max_v - min_v
        while heap:
            max_v = -heapq.heappop(heap)
            ans = min(ans, max_v - min_v)
            if max_v & 1 == 0:
                v = max_v >> 1
                heapq.heappush(heap, -v)
                min_v = min(min_v, v)
            else:
                return ans
        return -1
    # 有序表实现
    def minimumDeviation2(self, nums: List[int]) -> int:
        ss = SortedSet([num if num & 1 == 0 else num << 1 for num in nums])

        ans = float('inf')
        while ss:
            min_v = ss[0]
            max_v = ss.pop()
            ans = min(ans, max_v - min_v)
            if max_v & 1 == 0:
                ss.add(max_v >> 1)
            else:
                return ans
        return -1

# nums =[1,2,3,4]
nums =[8,1,2,1]
print(Solution().minimumDeviation2(nums))